package LeetCodeHot100TopInterview;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Q039_CombinationSum {
    static List<List<Integer>>  ans = null;
    //组合总数 ==> 合理的选择暴力递归模型 ==> 相减为 0
    //本题的难点在于如何去重 ==> 排序 ==> 同层级 左边已经使用的不再考虑 ==> 不懂画树
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
       if (candidates == null || candidates.length == 0){
           return null;
       }
       ans = new LinkedList<>();
       Arrays.sort(candidates);
       process(candidates, target, new LinkedList<>(), 0);
       return ans;
    }

    public void process(int[] candidates,  int rest, LinkedList<Integer> list, int index) {

        if (rest == 0){
            List<Integer> tmp = new LinkedList<>(list);
            ans.add(tmp);
            return;
        }

        //广度搜索
        for (int i = index; i < candidates.length; i++) {
            //剪枝叶
            if (rest - candidates[i] >= 0) {
                list.add(candidates[i]);
                process(candidates, rest - candidates[i], list, i);
                //恢复现场
                list.removeLast();
            }
        }
    }

    public static void main(String[] args) {
        Q039_CombinationSum fun = new Q039_CombinationSum();
        System.out.println(fun.combinationSum(new int[]{2, 3, 6, 7}, 7));
    }
}
